package it.unisa.ingegneria.tdp.esercitazione5;
import java.util.ArrayList;
import java.util.Iterator;

/**
 * Classe che implementa l'algoritmo di Kruskal
 */

public class Kruskal<T> {
	private Graph<T> grafo;
	private Graph<T> mst;
	private ArrayList<MyEdge<T>> archiMST;
	private int numVertici;
	
	public Kruskal(Graph<T> g)
	{
		this.grafo=g;
		archiMST = new ArrayList<MyEdge<T>>();
		mst = new Graph<T>();
		numVertici = grafo.getVertici().size();
	}
	
	public Graph<T> creaAlberoDiConnessioneMinimo()
	{
		definisciAlberoDiConnessioneMinimo();
		mst.setArchi(archiMST);
		mst.setVertici(grafo.getVertici());
		
		Iterator<MyEdge<T>> archiUscenti;
		MyEdge<T> temp;
		ArrayList<MyEdge<T>> archiUscentiDiMST;
		for(int i=0; i<numVertici; i++)
		{
			archiUscentiDiMST = (ArrayList<MyEdge<T>>) mst.getVertici().get(i).getOutgoigEdges();
			archiUscenti = mst.getVertici().get(i).getOutgoigEdges().iterator();
			while(archiUscenti.hasNext())
			{
				temp=archiUscenti.next();
				if(!mst.getArchi().contains(temp))
				{
					archiUscentiDiMST.remove(temp);
					archiUscenti = mst.getVertici().get(i).getOutgoigEdges().iterator();
				}
			}
			mst.getVertici().get(i).setOutgoingEdges(archiUscentiDiMST);
		}
		
		return mst;
	}
	
	private void definisciAlberoDiConnessioneMinimo()
	{
		ArrayList<MyVertex<T>> setVertici= new ArrayList<MyVertex<T>>();
		
		ArrayList<MyEdge<T>> archiDaEsaminare = (ArrayList<MyEdge<T>>)grafo.getArchi();
		MyEdge<T> min;
		MyVertex<T> u;
		MyVertex<T> v;
		int ottimizza=0;
	
		for(int i=0;i<numVertici;i++)
		{
			setVertici.add(i, grafo.getVertici().get(i));
		}
		
		while(!archiDaEsaminare.isEmpty() && ottimizza!=numVertici)
		{
			min = arcoAPesoMinimo(archiDaEsaminare);
			archiDaEsaminare.remove(min);
			u=min.getSource();
			v=min.getDrain();
			int posU=posizioneVerticeInSet(setVertici, u);
			int posV=posizioneVerticeInSet(setVertici, v);
		
			if(posU!=posV)
			{
				archiMST.add(min);
				ottimizza = ottimizza+1;
				setVertici.remove(v);
				setVertici.add(posU,v);
			}
		}
	}
	
	private int posizioneVerticeInSet(ArrayList<MyVertex<T>> setVertici, MyVertex<T> v)
	{
		int pos=-1;;
		
		for(int i=0; i<numVertici; i++)
		{
			if(setVertici.get(i).equals(v))
				pos=i;
		}
		return pos;
	}
	
	private MyEdge<T> arcoAPesoMinimo(ArrayList<MyEdge<T>> archiDaEsaminare)
	{
		Iterator<MyEdge<T>> i = archiDaEsaminare.iterator();
		MyEdge<T> minEdge=null;
		MyEdge<T> temp;
		
		if(i.hasNext())
		{
			minEdge=i.next();
			while(i.hasNext())
			{
				temp=i.next();
				int peso1 = (Integer)temp.getDecorator("weight");
				int peso2 = (Integer)minEdge.getDecorator("weight");
				if(peso1<peso2)
					minEdge=temp;
			}
		}
		return minEdge;
	}

}

